#include <iostream>
#include <vector>

using namespace std;

void merge(vector<int>& arr, int low, int high, int m){
    int p1 = low, p2 = m + 1, idx = 0;
    vector<int> temp(high - low + 1);
    while(p1 <= m && p2 <= high){
        temp[idx++] = (arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++]);
    }
    std::copy(arr.begin() + p1, arr.begin() + m + 1, temp.begin() + idx);
    std::copy(arr.begin() + p2, arr.begin() + high + 1, temp.begin() + idx);
    std::copy(temp.begin(), temp.end(), arr.begin() + low);
}

void mergeSort(vector<int>& arr, int low, int high){
    if(low < high){
        int m = (low + high) / 2;
        mergeSort(arr, low, m);
        mergeSort(arr, m + 1, high);
        merge(arr, low, high, m);
    }
}

int main(){
    vector<int> arr = {3,1,4,5,6,7,9,0};
    mergeSort(arr, 0, arr.size() - 1);
    for(int& x : arr){
        cout << x << " ";
    }
    return 0;
}